In this I'm going to go through the implamentation of the a heap and a heap sort. A heap is just a list that you can visulize as a binary tree structure.
for a heap to be valid it must each node must be less than it's parent node.
66
/ \
44 33
/ \
25 20
This is actually stored in an array usually, for reduced memory concuption and simplicity. In the array representation these elements woulb be: [66, 44, 33, 25, 20]. it's from right to left, top to bottom.
to get the relitive root of your current node (assuming it's not the root): floor((current node index - 1)/2) to get the left child: (2 current node index + 1) to get the right child (2 current node index + 2)
Note: heaps are not orderd like BST's where there's an implied, right is greater than left, relatiohsip. In a heap there are two possible oreantations: Max Heap, or Min Heap. Max heap is where every parent node is greater than or equal to the child nodes. Min Heap is the oppisite.
the wiki artical) on Heaps is very helpful. Also this youtube video was vary useful.
In [14]:
import random
heap_input_list = []
for i in range(0, 15):
heap_input_list.append(random.randint(0, 100)) # pick a random integer nuber between 0 and 100 and add it to our test array
# A right bitshift by one is equevelnet to dooubling a noumber.
# A left bit shift is equvelent to deviding by two (obviously only in an integer way)????
class Heap(object):
def __init__(self, input: list):
self.heap = input
self.n = len(self.heap) - 1
self.heapify()
def __repr__(self):
return str(self.heap)
@staticmethod
def parent(index: int):
return (index - 1) >> 1
@staticmethod
def left_child(index: int):
return (index << 1) + 1
@staticmethod
def right_child(index: int):
return (index << 1) + 2
def max_heapify(self, index):
# heap_size = len(self.heap)
left_idx = self.left_child(index)
right_idx = self.right_child(index)
if left_idx < self.n and right_idx < self.n:
if self.heap[index] < self.heap[right_idx] or self.heap[index] < self.heap[left_idx]:
if self.heap[left_idx] > self.heap[right_idx]:
self.swap(left_idx, index)
self.max_heapify(left_idx)
else:
self.swap(right_idx, index)
self.max_heapify(right_idx)
elif left_idx < self.n and self.heap[index] < self.heap[left_idx]:
self.swap(left_idx, index)
def swap(self, index1, index2):
temp = self.heap[index1]
self.heap[index1] = self.heap[index2]
self.heap[index2] = temp
def heapify(self):
last_root = self.parent(len(self.heap) - 1)
for i in range(last_root, -1, -1):
self.max_heapify(index=i)
def is_valid(self):
index = len(self.heap) - 1
while index > -1:
parent_index = self.parent(index)
if parent_index > -1:
if self.heap[index] > self.heap[parent_index]:
return False
index -= 1
return True
# heap sort is dead simple once you get the basic heap implementation in place.
def sort(self):
for i in range(self.n, 1, -1):
self.swap(0, i)
self.n -= 1
self.max_heapify(0)
# reset n
self.n = len(self.heap)
temp = [1, 5, 10, 15, 20, 25, 17, 14, 8, 99, 81, 85, 9, 12]
heap = Heap(temp)
print(heap)
# print(heap.is_valid())
heap.sort()
print(heap)
In [ ]: